/*
Baidu Interview question

Given a function Random(5),
which will return a number of {1, 2, 3, 4, 5} by random, 
then how to implement a function of random(n)?

Answer:
Suppose you have Random(10), which returns {0..9}. You can easily make Random(1000) by calling Random(10) three times and concatenating the results, right?

Lemma 2 says you can do the same thing for any N, if you treat the concatenated result as a number in base-N. Just as concatenating results of Random(10) gets you a base 10 number, concatenating results from Random(2) will get you a binary number, and so on. In general concatenating the results of Y calls to Random(X) forms a base X number in the range [0..X^Y].

Thus, if we call Random(5) seven times, and label the results R0..R6, then we can find:
  R = R0 + R1*5 + R2*25 + .... + R6*5^6
  and R will be an even distribution over [0..5^7]. 
*/
#include "junix.h"

int random5() { return rand()%5+1; }

//junix's solution
int random_n(int n) 
{
	int factor = 5;
	int times = 1;
	while (factor<n)
   	{
		factor *= 5;
		++times;
	}

	int div = factor/n;
	int upper_bound = n*div;
	int vec[times];
	int index = 0;

	while (true)
   	{
		for(int i=0;i<times;i++) 
			vec[i]=random5();

		index = 0;
		for(int i=0;i<times;i++)
			index = index*5+vec[i];

		if (index>upper_bound)
			continue;

		return index%n+1;
	}
}

int main()
{
	int sz = 30;
	srand(time(NULL));
	std::vector<int> V;
	V.reserve(sz);
	for (int i=0;i<sz;i++)
		V.push_back(random_n(sz));

	std::sort(V.begin(),V.end());
	std::copy(V.begin(),V.end(),std::ostream_iterator<int>(std::cout," "));
	std::cout<<std::endl;
}
